NOTICE: This article originally appeared in the October, '88 issue of MichiganAtari Magazine and may be freely distributed or reprinted in non-profit UserGroup publications as long as the article's author and Michigan Atari Magazineare credited AND this notice is reprinted with the article. All otherpublications must obtain written permission from Unicorn Publications, 3487Braeburn Circle, Ann Arbor, MI 48108, Phone: (313) 973-8825 before using thisarticle.The Sport of Sortsby Clinton Pierce (GAG)In this installment we're going to look at one of the most fundamentalproblems in computers, sorting. Human beings, as a rule, have an amazingsense of geometric perception. They will sort index cards with names on themby placing the names in relative order on the table (A is a lot farther awayfrom P, than M is), and doing fine adjustments as they go along.Computers aren't human. They must sort using absolutes. You must tell themwhat is to be sorted (records), how it is to be sorted (keys), and where it isto go to (output). And they can only compare (again, as a rule) two things ata time.The first sort is the standard Hey-I-learned-that-in-BASIC sort: the bubblesort. The bubble sort compares two elements in an array, and if they are inthe wrong order, swiches them around. It is finished when either n^2repetitions have occured, or when no more switches are made in an entirepass.The next sort is Shell's sort (named after a man, not the method). APseudo-BASIC program follows for an array a, N elements long: 1.M=N 2.M=Intger part of M/2, If m=0 then the sort is done else: J=1, K=N-M 3. I=J 4.L=I+M, If a(i)<a(l) then goto step 6, else: T=a(i), a(i)=a(l), a(l)=T, I=I-M,if I<1 Then goto step 6 5. Goto Step 4 6. J=J+1, if J<=K then goto step 3 7.Go To step #1.This sort is fairly fast, and is fairly uncomplex. However, it has itsproblems. Two identical elements will be switched (always). Because of that,if the list has many similar elements, find another sort. (About line #2, aone element array, by definition, is sorted).Next, we have the Selection sort (which, as we will see in the future lendsitself to recursion). Take the same array A with N elements, and set apointer Q equal to the number of elements. Algorythm: If q=1 then the arrayis sorted, else : Find the largest element in the subset (1..Q-1) and switchit with the Qth element, decrease Q by one, go back and repeat it again. Thissort is fast, but does not deal well with an already sorted list.The Insertion sort can be done one of two ways, with one array, or two. Forsimplicity, I'll present the two-array version. Clear the second array Z, andset the pointers Q & X to 0. #1 Move the first element of A into Z, andincrease the pointers. #2 Take the Xth element in A, Find out where it goesin Z, and move everything in Z > a(x) down one element, make z(q)=a(x),Increase X and Q. #3 Go to step 2 until q=N. This sort is moderately fast.Next, Quicksort, is the fastest sort I've dealt with. A complete algorythmwill not be given until the unit on Recursion. But here's how it works: Givenan array 1..N, arrange the array so that all values < a pivot value, arefirst, and > pivot are last. Then, the pivot is in its proper place. It isthen done again, and again, using each smaller region until the array issorted. The sort is incredibly fast. The number of passes needed is only Ntimes the Base-2 log of N. (Where bubblesort would use 4096 repetitions,quicksort uses 384).Until next time....Hasta Luego.
